﻿//class Solution
//{
//	vector<int> ret;
//	vector<int> index; // 记录 nums 中当前元素的原始下标
//	int tmpNums[500010];
//	int tmpIndex[500010];
//public:
//	vector<int> countSmaller(vector<int>& nums)
//	{
//		int n = nums.size();
//		ret.resize(n);
//		index.resize(n);
//		// 初始化⼀下 index 数组
//		for (int i = 0; i < n; i++)
//			index[i] = i;
//			mergeSort(nums, 0, n - 1);
//		return ret;
//	}
//	void mergeSort(vector<int>& nums, int left, int right)
//	{
//		if (left >= right) return;
//		// 1. 根据中间元素，划分区间
//		int mid = (left + right) >> 1;
//		// [left, mid]  [mid + 1, right]
//		// 2. 先处理左右两部分
//		mergeSort(nums, left, mid);
//		mergeSort(nums, mid + 1, right);
//		// 3. 处理⼀左⼀右的情况
//		int cur1 = left, cur2 = mid + 1, i = 0;
//		while (cur1 <= mid && cur2 <= right) // 降序
//		{
//			if (nums[cur1] <= nums[cur2])
//			{
//				tmpNums[i] = nums[cur2];
//				tmpIndex[i++] = index[cur2++];
//			}
//			else
//			{
//				ret[index[cur1]] += right - cur2 + 1; // 重点
//				tmpNums[i] = nums[cur1];
//				tmpIndex[i++] = index[cur1++];
//			}
//		}
//		// 4. 处理剩下的排序过程
//		while (cur1 <= mid)
//		{
//			tmpNums[i] = nums[cur1];
//			tmpIndex[i++] = index[cur1++];
//		}
//		while (cur2 <= right)
//		{
//			tmpNums[i] = nums[cur2];
//			tmpIndex[i++] = index[cur2++];
//		}
//		for (int j = left; j <= right; j++)
//		{
//			nums[j] = tmpNums[j - left];
//				index[j] = tmpIndex[j - left];
//		}
//	}
//};